package org.apache.commons.graph.view

import org.apache.commons.graph.view.iterator.GraphBreadthFirstIterator
import org.apache.commons.graph.view.iterator.GraphDepthFirstIterator
import org.apache.commons.graph.view.iterator.TopologicalOrderIterator
import org.apache.commons.graph.visitor.ITargetVertexVisitor


interface ITargetVertexView<V> : ITargetVertexVisitor<V> {
    fun vertexSet(): Collection<V>

    val isEmpty: Boolean
        get() = vertexSet().isEmpty()

    fun containsVertex(vertex: V): Boolean {
        return vertexSet().contains(vertex)
    }

    fun topologicalOrderIterator(allowLoop: Boolean): TopologicalOrderIterator<V> {
        return TopologicalOrderIterator(vertexSet(), this, allowLoop)
    }

    fun reachableVertexes(vertex: V): Set<V> {
        val set = LinkedHashSet<V>()
        GraphBreadthFirstIterator.reachable(set, this, vertex)
        return set
    }

    fun findCycles(): Set<V> {
        return CycleDetector(this).findCycles()
    }

    fun depthFirstIterator(start: V): Iterator<V> {
        return GraphDepthFirstIterator(this, start)
    }

    fun breadthFirstIterator(start: V): Iterator<V> {
        return GraphBreadthFirstIterator(this, start)
    }
}

/**
 * Detects cycles in directed graphs.
 *
 * @param <V> Vertex type
</V> */
class CycleDetector<V>(private val graph: ITargetVertexView<V>) {
    // 这个Set可能包含多余的节点，并不是最简化的循环链
    fun findCycles(): Set<V> {
        return TopologicalOrderIterator(graph.vertexSet(), graph, false).findCycles()
    }
}